package com.yoshino.leetcode.interview150.interval;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<>();
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            int j = i;
            StringBuilder str = new StringBuilder();
            while (j < length - 1 && nums[j] + 1 == nums[j + 1]) {
                j++;
            }
            str.append(nums[i]);
            if (j != i) {
                str.append("->").append(nums[j]);
                i = j;
            }
            res.add(str.toString());
        }
        return res;
    }

    public int[][] merge(int[][] intervals) {
        if (intervals.length == 1) {
            return intervals;
        }
        // 根据第一个数排序
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        List<int[]> temp = new ArrayList<>();
        int left, right, length = intervals.length;
        for (int i = 0; i < length; i++) {
            left = intervals[i][0];
            right = intervals[i][1];
            while (i < length - 1 && right >= intervals[i + 1][0]) {
                i++;
                right = Math.max(right, intervals[i][1]);
            }
            temp.add(new int[]{left, right});
        }
        return temp.toArray(new int[0][0]);
    }

    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals.length == 0) {
            return new int[][]{{newInterval[0], newInterval[1]}};
        }
        List<int[]> temp = new ArrayList<>();
        int left = newInterval[0], right = newInterval[1], length = intervals.length;
        boolean flag = false;
        for (int i = 0; i < length; i++) {
            if (flag || intervals[i][1] < left) {
                temp.add(intervals[i]);
            } else if (intervals[i][0] > right){
                // 需要放置
                flag = true;
                temp.add(new int[]{left, right});
                temp.add(intervals[i]);
            } else {
                left = Math.min(left, intervals[i][0]);
                right = Math.max(right, intervals[i][1]);
            }
        }
        // 刚好为最外层
        if (!flag) {
            temp.add(new int[]{left, right});
        }
        return temp.toArray(new int[0][0]);
    }

    public int findMinArrowShots(int[][] points) {
        if (points.length == 1) {
            return 1;
        }
        // 先排序，找到下一个左边界大于右边界
        Arrays.sort(points, Comparator.comparingInt(a -> a[0]));
        int right = points[0][1], res = 0;
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > right) {
                // 超过
                right = points[i][1];
                res++;
            } else {
                right = Math.min(right, points[i][1]);
            }
        }
        res++;
        return res;
    }
}